#include "TTToeBoard.h"
#include "TTToeState.h"
#include "TTToePosition.h"
#include <cstdio>
#include <list>
#include <random>
#include <iostream>
#include <string>
#include <regex>

#define		REGEX_ARRAY_LENGTH			8
#define		DEFAULT_MAX_DEPTH			3
#define		DEFAULT_BRANCHES			2
#define		STATE_THRESHOLD				1538

namespace SmartTTToe {
	TTToeBoard::TTToeBoard(int size) :
		boardMap(NULL),
		evalBoard(NULL),
		TScore(NULL),
		KScore(NULL),
		stateArray(NULL),
		regex_points(NULL)
	{
		this->boardSize = size;
		this->stepCount = 0;
		this->branches = DEFAULT_BRANCHES;
		this->maxDepth = DEFAULT_MAX_DEPTH;


		// Initialize TScore and KScore
		this->TScore = new int[5];
		this->TScore[0] = 0;
		this->TScore[1] = 1;
		this->TScore[2] = 9;
		this->TScore[3] = 85;
		this->TScore[4] = 769;
		this->KScore = new int[5];
		this->KScore[0] = 0;
		this->KScore[1] = 4;
		this->KScore[2] = 28;
		this->KScore[3] = 256;
		this->KScore[4] = 2308;

		// Initialize board map
		this->boardMap = new char*[size];
		for (int i = 0; i < size; i++) {
			this->boardMap[i] = new char[size];
		}
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				this->boardMap[i][j] = PLAYER_NONE;
			}
		}

		// Initialize the evalBoard
		this->evalBoard = new int*[size];
		for (int i = 0; i < size; i++) {
			this->evalBoard[i] = new int[size];
		}
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				this->evalBoard[i][j] = 0;
			}
		}

		// Initialize the stateArray
		this->stateArray = new TTToeState**[size];
		for (int i = 0; i < size; i++) {
			this->stateArray[i] = new TTToeState*[size];
		}
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				this->stateArray[i][j] = new TTToeState();
			}
		}

		// Initialize xCases for regex
		this->xCases = new std::string[REGEX_ARRAY_LENGTH]; //{"\\sxx\\s", "\\sxxxo", "oxxx\\s", "\\sxxx\\s", "\\sxxxxo", "oxxxx\\s", "\\sxxxx\\s", "xxxxx"};
		this->xCases[0] = "\\sxx\\s";
		this->xCases[1] = "\\sxxxo";
		this->xCases[2] = "oxxx\\s";
		this->xCases[3] = "\\sxxx\\s";
		this->xCases[4] = "\\sxxxxo";
		this->xCases[5] = "oxxxx\\s";
		this->xCases[6] = "\\sxxxx\\s";
		this->xCases[7] = "xxxxx";
		this->oCases = new std::string[REGEX_ARRAY_LENGTH]; //{"\\soo\\s", "\\sooox", "xooo\\s", "\\sooo\\s", "\\soooox", "xoooo\\s", "\\soooo\\s", "ooooo"};
		this->oCases[0] = "\\soo\\s";
		this->oCases[1] = "\\sooox";
		this->oCases[2] = "xooo\\s";
		this->oCases[3] = "\\sooo\\s";
		this->oCases[4] = "\\soooox";
		this->oCases[5] = "xoooo\\s";
		this->oCases[6] = "\\soooo\\s";
		this->oCases[7] = "ooooo";
		// Initialize the regex points
		this->regex_points = new int[REGEX_ARRAY_LENGTH] {6, 4, 4, 12, 30, 30, 3000, 10000};
	}

	TTToeBoard::~TTToeBoard(void) {
		// Free the TScore and KScore
		if (this->TScore) {
			delete[] this->TScore;
			this->TScore = NULL;
		}
		if (this->KScore) {
			delete[] this->KScore;
			this->KScore = NULL;
		}

		// Free the board map
		if (this->boardMap) {
			for (int i = 0; i < this->boardSize; i++) {
				delete[] this->boardMap[i];
			}
			delete[] this->boardMap;
			this->boardMap = NULL;
		}

		// Free the evaluation board
		if (this->evalBoard) {
			for (int i = 0; i < this->boardSize; i++) {
				delete[] this->evalBoard[i];
			}
			delete[] this->evalBoard;
			this->evalBoard = NULL;
		}

		// Free the stateArray
		if (this->stateArray) {
			for (int i = 0; i < this->boardSize; i++) {
				for (int j = 0; j < this->boardSize; j++) {
					delete this->stateArray[i][j];
				}
				delete[] this->stateArray[i];
			}
			delete[] this->stateArray;
		}

		// Free the regex paterns
		// TODO (Minh Luan): complete this

		// Free the regex points
		if (this->regex_points) {
			delete[] this->regex_points;
			this->regex_points = NULL;
		}
	}

	int TTToeBoard::insert(int x, int y, bool turn) {
		if (x >= this->boardSize ||
			y >= this->boardSize ||
			x < 0 ||
			y < 0) {
			// Error insertion
			return -1;
		}
		else {
			this->stepCount++;
			if (turn) {
				this->boardMap[x][y] = PLAYER_2_;
			}
			else {
				this->boardMap[x][y] = PLAYER_1_;
			}
		}
		return 0;
	}

	int TTToeBoard::getBranches() {
		return this->branches;
	}

	void TTToeBoard::setBranches(int branches) {
		this->branches = branches;
	}

	int TTToeBoard::getMaxDepth() {
		return this->maxDepth;
	}

	void TTToeBoard::setMaxDepth(int maxDepth) {
		this->maxDepth = maxDepth;
	}

	// ******************************************************
	// Private function
	// ******************************************************
	void TTToeBoard::evaluateBoard(char** cells, char player) {

		// Initialize the evaluation board
		for (int i = 0; i < this->boardSize; i++) {
			for (int j = 0; j < this->boardSize; j++) {
				this->evalBoard[i][j] = 0;
			}
		}

		for (int i = 0; i < this->boardSize; i++) {
			for (int j = 0; j < this->boardSize; j++) {
				if (this->boardMap[i][j] != PLAYER_NONE) {
					this->evalBoard[i][j] = -1;
				}
			}
		}

		int player1Counter;
		int player2Counter;

		// Checking row
		for (int row = 0; row < this->boardSize; row++) {
			for (int col = 0; col < this->boardSize - 4; col++) {
				player1Counter = 0;
				player2Counter = 0;
				for (int i = 0; i < 5; i++) {
					if (cells[row][col + i] == PLAYER_1_) {
						player1Counter++;
					}
					if (cells[row][col + i] == PLAYER_2_) {
						player2Counter++;
					}
				}

				if ((player1Counter * player2Counter == 0) && (player1Counter != player2Counter)) {
					for (int i = 0; i < 5; i++) {
						if (cells[row][col + i] == PLAYER_NONE) {
							if (player == PLAYER_1_) {
								this->evalBoard[row][col + i] += this->TScore[player1Counter];
							}
							else {
								this->evalBoard[row][col + i] += this->KScore[player1Counter];
							}

							if (player == PLAYER_2_) {
								this->evalBoard[row][col + i] += this->TScore[player2Counter];
							}
							else {
								this->evalBoard[row][col + i] += this->KScore[player2Counter];
							}

							if (player1Counter == 4 || player2Counter == 4) {
								this->evalBoard[row][col + i] <<= 1;
							}
						}
					}
				}
			}
		}	// End checking row



		// Check column
		for (int row = 0; row < this->boardSize - 4; row++) {
			for (int col = 0; col < this->boardSize; col++) {
				player1Counter = 0;
				player2Counter = 0;
				for (int i = 0; i < 5; i++) {
					if (this->boardMap[row + i][col] == PLAYER_1_) {
						player1Counter++;
					}
					if (this->boardMap[row + i][col] == PLAYER_2_) {
						player2Counter++;
					}
				}

				if (player1Counter * player2Counter == 0 && player1Counter != player2Counter) {
					for (int i = 0; i < 5; i++) {
						if (cells[row + i][col] == PLAYER_NONE) {
							if (player == PLAYER_1_) {
								this->evalBoard[row + i][col] += this->TScore[player2Counter];
							}
							else {
								this->evalBoard[row + i][col] += this->KScore[player2Counter];
							}
							if (player == PLAYER_2_) {
								this->evalBoard[row + i][col] += this->TScore[player1Counter];
							}
							else {
								this->evalBoard[row + i][col] += this->KScore[player1Counter];
							}
							if (player1Counter == 4 || player2Counter == 4) {
								this->evalBoard[row + i][col] <<= 1;
							}
						}
					}
				}
			}
		}	// End checking column

		// Duong cheo xuong
		for (int row = 0; row < this->boardSize - 4; row++) {
			for (int col = 0; col < this->boardSize - 4; col++) {
				player1Counter = 0;
				player2Counter = 0;
				for (int i = 0; i < 5; i++) {
					if (cells[row + i][col + i] == PLAYER_1_) player1Counter++;
					if (cells[row + i][col + i] == PLAYER_2_) player2Counter++;
				}

				if (player1Counter * player2Counter == 0 && player1Counter != player2Counter) {
					for (int i = 0; i < 5; i++){
						if (cells[row + i][col + i] == PLAYER_NONE)	{
							if (player == PLAYER_1_) {
								this->evalBoard[row + i, col + i] += TScore[player2Counter];
							}
							else {
								this->evalBoard[row + i, col + i] += KScore[player2Counter];
							}
							if (player == PLAYER_2_) {
								this->evalBoard[row + i][col + i] += TScore[player1Counter];
							}
							else {
								this->evalBoard[row + i, col + i] += KScore[player1Counter];
							}
							if (player1Counter == 4 || player2Counter == 4) {
								this->evalBoard[row + i][col + i] <<= 1;
							}
						}
					}
				}
			}
		}	// End checking duong cheo xuong

		//Duong cheo len
		for (int row = 4; row < this->boardSize; row++) {
			for (int col = 0; col < this->boardSize - 4; col++)
			{
				player1Counter = 0;
				player2Counter = 0;
				for (int i = 0; i < 5; i++)
				{
					if (cells[row - i][col + i] == PLAYER_2_) player2Counter++;
					if (cells[row - i][col + i] == PLAYER_1_) player1Counter++;
				}

				if (player2Counter * player1Counter == 0 && player2Counter != player1Counter) {
					for (int i = 0; i < 5; i++) {
						if (cells[row - i][col + i] == PLAYER_NONE)	{
							if (player == PLAYER_2_) {
								this->evalBoard[row - i][col + i] += this->TScore[player1Counter];
							}
							else {
								this->evalBoard[row - i][col + i] += this->KScore[player1Counter];
							}
							if (player == PLAYER_1_) {
								this->evalBoard[row - i][col + i] += this->TScore[player2Counter];
							}
							else {
								this->evalBoard[row - i][col + i] += this->KScore[player2Counter];
							}
							if (player1Counter == 4 || player2Counter == 4)
								this->evalBoard[row - i][col + i] <<= 1;
						}
					}
				}
			}
		}	// End checking duong cheo len
	}


	TTToeState* TTToeBoard::GetMaxNode() {
		TTToePosition* p = new TTToePosition(0, 0);
		std::list<TTToeState*> stateList;
		int t = INT_MIN;
		for (int i = 0; i < this->boardSize; i++) {
			for (int j = 0; j < this->boardSize; j++) {
				if (t < this->evalBoard[i][j]) {
					t = this->evalBoard[i][j];
					p->SetX(i);
					p->SetY(j);
					stateList.clear();
					this->stateArray[i][j]->SetState(p, t);
					stateList.push_back(this->stateArray[i][j]);
				}
				else if (t == this->evalBoard[i][j]){
					p->SetX(i);
					p->SetY(j);
					this->stateArray[i][j]->SetState(p, t);
					stateList.push_back(this->stateArray[i][j]);
				}
			}
		}

		// Free the temporal position variable
		delete p;
		p = NULL;

		for (std::list<TTToeState*>::iterator it = stateList.begin(); it != stateList.end(); it++) {
			TTToeState* currentState = (*it);
			this->evalBoard[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = 0;
		}

		std::random_device rd;
		std::mt19937 gen(rd());
		std::uniform_int_distribution<> dis(1, stateList.size() - 1);
		int dice_roll = dis(gen);
		for (std::list<TTToeState*>::iterator it = stateList.begin(); it != stateList.end(); it++) {
			if (dice_roll <= 0) {
				return (*it);
			}
			dice_roll--;
		}

		// Cannot reach this place
		return NULL;
	}

	int TTToeBoard::Evaluate() {
		std::string s = "";
		for (int i = 0; i < this->boardSize; i++) {
			for (int j = 0; j < this->boardSize; j++) {
				s += this->boardMap[i][j];
			}
			s += ";";
			for (int j = 0; j < this->boardSize; j++) {
				s += this->boardMap[j][i];
			}
			s += ";";
		}

		for (int i = 0; i < this->boardSize - 4; i++) {
			for (int j = 0; j < this->boardSize - i; j++) {
				s += this->boardMap[j][i + j];
			}
			s += ";";
		}
		for (int i = this->boardSize - 5; i > 0; i--) {
			for (int j = 0; j < this->boardSize - i; j++) {
				s += this->boardMap[i + j][j];
			}
			s += ";";
		}
		for (int i = 4; i < this->boardSize; i++) {
			for (int j = 0; j <= i; j++) {
				s += this->boardMap[i - j][j];
			}
			s += ";";
		}
		for (int i = this->boardSize - 5; i > 0; i--) {
			for (int j = this->boardSize - 1; j >= i; j--) {
				s += this->boardMap[j][i + this->boardSize - j - 1];
			}
			s += ";\n";
		}

		// Do the regex
		int mark = 0;
		for (int i = 0; i < REGEX_ARRAY_LENGTH; i++)
		{
			std::regex regex1(this->xCases[i]);
			std::regex regex2(this->oCases[i]);

			std::smatch match1, match2;
			std::regex_search(s, match1, regex1);
			std::regex_search(s, match2, regex2);

			mark -= this->regex_points[i] * match2.length();
			mark += this->regex_points[i] * match1.length();
		}

		return mark;
	}

	int TTToeBoard::MaxEvaluatedValue(TTToeState* state, int alpha, int beta, int depth) {
		int val = this->Evaluate();
		if (depth >= this->getMaxDepth() || std::abs(val) > 3000) return val;
		this->evaluateBoard(this->boardMap, PLAYER_2_);
		std::list<TTToeState*> stateList;
		for (int i = 0; i < this->getBranches(); i ++) {
			TTToeState* maxState = this->GetMaxNode();
			stateList.push_back(maxState);
			if (maxState->GetValue() > STATE_THRESHOLD) break;
		}
		for (std::list<TTToeState*>::iterator it = stateList.begin(); it != stateList.end(); it++) {
			TTToeState* currentState = *it;
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_2_;
			alpha = std::max(alpha, this->MinEvaluatedValue(currentState, alpha, beta, depth + 1));
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_NONE;
			if (alpha > beta) {		// TODO: check this condition
				break;
			}
		}
		return alpha;
	}

	int TTToeBoard::MinEvaluatedValue(TTToeState* state, int alpha, int beta, int depth) {
		int val = this->Evaluate();
		if (depth >= this->getMaxDepth() || std::abs(val) > 3000) return val;
		this->evaluateBoard(this->boardMap, PLAYER_1_);
		std::list<TTToeState*> stateList;
		for (int i = 0; i < this->getBranches(); i++) {
			TTToeState* maxState = this->GetMaxNode();
			stateList.push_back(maxState);
			if (maxState->GetValue() > STATE_THRESHOLD) break;
		}
		for (std::list<TTToeState*>::iterator it = stateList.begin(); it != stateList.end(); it++) {
			TTToeState* currentState = *it;
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_1_;
			beta = std::min(beta, MaxEvaluatedValue(currentState, alpha, beta, depth + 1));
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_NONE;
			if (alpha >= beta) {	// TODO: check this condition
				break;
			}
		}
		return beta;
	}

	TTToePosition* TTToeBoard::Solve() {
		// Evaluate the board
		this->evaluateBoard(this->boardMap, PLAYER_2_);
		std::list<TTToeState*> stateList;
		for (int i = 0; i < this->getBranches(); i++)
		{
			//list.Add(GetMaxNode(val));
			TTToeState* maxState = GetMaxNode();
			stateList.push_back(maxState);
			if (maxState->GetValue() > STATE_THRESHOLD) {
				break;
			}
		}

		int maxXP = INT_MIN;
		std::list<TTToeState*> choosingList;
		for (std::list<TTToeState*>::iterator it = stateList.begin(); it != stateList.end(); it++) {
			TTToeState* currentState = *it;
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_2_;
			int evaluatedValue = this->MinEvaluatedValue(currentState, INT_MIN, INT_MAX, 0);
			if (maxXP < evaluatedValue) {
				maxXP = evaluatedValue;
				choosingList.clear();
				choosingList.push_back(currentState);
			}
			else if (maxXP == evaluatedValue) {
				choosingList.push_back(currentState);
			}
			this->boardMap[currentState->GetPosition()->GetX()][currentState->GetPosition()->GetY()] = PLAYER_NONE;
		}

		std::random_device rd;
		std::mt19937 gen(rd());
		std::uniform_int_distribution<> dis(1, choosingList.size() - 1);
		int dice_roll = dis(gen);
		for (std::list<TTToeState*>::iterator it = choosingList.begin(); it != choosingList.end(); it++) {
			TTToeState* currentState = *it;
			if (dice_roll <= 0) {
				return currentState->GetPosition();
			}
			dice_roll--;
		}
		return NULL;	// Not going here
	}

	
}	// namespace SmartTTToe
